#include"DoubleLinkList.h"

DLinkList add(DLinkList L1, DLinkList L2) 
{
	string s1=LinkListToStr(L1);
	string s2 = LinkListToStr(L2);
	int i = s1.size() - 1;
	int j = s2.size() - 1;
	int add = 0;
	string ss = "";
	while (i >= 0 || j >= 0 || add != 0) {
		if (i >= 0)
			add = add + s1[i--] - '0';
		if (j >= 0)
			add = add + s2[j--] - '0';
		ss = ss + to_string(add % 10);
		add = add / 10;
	}
	reverse(ss.begin(), ss.end());
	DLinkList res=StrToLinkList(ss);
	return res;
}


//大数减法 
DLinkList sub(DLinkList L1, DLinkList L2) 
{
	string s1 = LinkListToStr(L1);
	string s2 = LinkListToStr(L2);
	bool minus = false;
	if (s1.size() < s2.size() || (s1.size() == s2.size() && s1 < s2)) {
		swap(s1, s2);
		minus = true;
	}
	int i = s1.size() - 1;
	int j = s2.size() - 1;
	int flag = 0;
	string ans = "";
	while (i >= 0 && j >= 0) {
		int tmp = 0;
		if (s1[i] >= s2[j]) {
			tmp = s1[i] - s2[j];
			tmp = tmp - flag;
			ans += to_string(tmp);
			flag = 0;
		}
		else {
			tmp = s1[i] - s2[j] + 10;
			tmp = tmp - flag;
			ans += to_string(tmp);
			flag = 1;
		}
		i--;
		j--;
	}
	// 处理较大数的剩余部分 
	while (i >= 0) {
		if (flag == 0) {
			ans += s1[i];
		}
		else {
			int tmp = s1[i] - '0' - flag;
			ans += to_string(tmp);
			flag = 0;
		}
		i--;
	}
	// 翻转 
	reverse(ans.begin(), ans.end());
	//去除前导 0 
	int k = 0;
	while (k < ans.size() && ans[k] == '0') k++;
	if (k == ans.size()) {
		ans = "0";
	}
	else ans = ans.substr(k);
	// 结果是否为负 
	minus ? ans="-" + ans : ans;
	DLinkList ans_LinkList = StrToLinkList(ans);
	return ans_LinkList;
}


//大数乘法
//使用大小为 n + m 的数组，str1的第i位乘以str2的第j位，结果对应存放在数组的i + j + 1的位置。（竖式乘法）
DLinkList multiply(DLinkList L1, DLinkList L2)
{
	string str1 = LinkListToStr(L1);
	string str2 = LinkListToStr(L2);
	int n = str1.size();
	int m = str2.size();
	vector<int> result(n + m, 0);
	for (int i = n - 1; i >= 0; i--) {
		for (int j = m - 1; j >= 0; j--) {
			int tmp = (str1[i] - '0') * (str2[j] - '0');    //保存每一位乘法运算结果
			tmp += result[i + j + 1];     //由于为竖式乘法，故每次遍历str1的每个字符时都会进行一次遍历str2，需把每次遍历str1每个字符得到的result数组加起来
			//计算上一位(带进位)后乘法运算结果
			result[i + j] += tmp / 10;       //注意 这里是 +=，因为上一位是进位，需加上上一位原来的数字
			//计算该位(带进位)后乘法运算结果
			result[i + j + 1] = tmp % 10;
		}
	}
	//去除前导0
	int i = 0;
	while (i < n + m && result[i] == 0) {
		i++;
	}
	string ans;
	for (; i < n + m; i++) {
		ans.push_back(result[i] + '0');
	}

	ans.size() == 0 ? ans="0" : ans;   //使乘法结果为0时返回"0"
	
	DLinkList ans_L = StrToLinkList(ans);
	return ans_L;
}


//字符串除法(待修改，有bug)
//DLinkList divide(DLinkList L1, DLinkList L2) 
//{
//	string str1 = LinkListToStr(L1);
//	string str2 = LinkListToStr(L2);
//	int remainder = 0;//需要保存余数 
//	for (int i = 0; i < str1.size(); ++i) {
//		int current = remainder * 10 + str1[i] - '0';
//		str1[i] = current / stoi(str2) + '0';
//		remainder = current % stoi(str2);
//	}
//	int pos = 0;//查找首个非0下标 
//	while (str1[pos] == '0') {
//		pos++;
//	}
//	DLinkList res = StrToLinkList(str1.substr(pos));
//	return res;//删除前置的多余0 
//}

